package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.Arrays;

/***
 * 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，
 * 要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，
 * 等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，
 * 分别是等于K的数组部分的左右两个下标值。
 *
 * 例如，给定数组：[2, 3, 1, 9, 7, 6, 1, 4, 5]，
 * 给定一个值4，那么经过处理原数组
 * 可能得一种情况是：[2, 3, 1, 1, 4, 9, 7, 6, 5]，需要注意的是，
 * 小于4的部分不需要有序，大于4的部分也不需要有序，
 * 返回等于4部分的左右两个下标，即[4, 4]
 *

 */
public class Day24_4 {

    public static int[] partition(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return new int[]{0, 0};
        }
        //lessThan左边的区间表示小于num
        int lessThan = -1;
        //moreThan右边表示大于num
        int moreThan = arr.length;
        //记录当前遍历位置
        int index = 0;
        //如果没有和大于区域交叉  表示还有数处于待定
        while (index < moreThan) {
            if (arr[index] < num) {
                ArrayUtils.swap(arr, index, lessThan + 1);
                lessThan++;
                index++;
            } else if (arr[index] == num) {
                index++;
            } else {
                ArrayUtils.swap(arr, index, moreThan - 1);
                moreThan--;
            }
        }
        return new int[]{lessThan + 1, moreThan};
    }


    public static void main(String[] args) {
        int[] arr = {2, 1, 4, 3, 7, 5, 5, 5, 5, 6, 0, 9};
        int num = 5;
        int[] ints = partition(arr, num);
        System.out.println(Arrays.toString(arr));
        ArrayUtils.print(ints);
        ArrayUtils.print(arr, ints[0], ints[1]);
    }


}
